
/* class encapsulating a code derived from 
Gary McGuire's method of fast finding of all UA of size up to 12
applied to X+Y+27 (band1 filled) where each UA is in a 32bits field
*/
#include "t_128.h"

class BF128:public bm128{// using 128 bits as of mladen dobrichev with special services
public:
	inline void Load(BF3 &ua,BF3 & ndead){
		bitmap128.m128i_u32[3]=0;
		bitmap128.m128i_u32[0]=ua.bf[0] & ndead.bf[0];
		bitmap128.m128i_u32[1]=ua.bf[1] & ndead.bf[1];
		bitmap128.m128i_u32[2]=ua.bf[2] & ndead.bf[2];
	}
	inline void Load(BF3 &ua){
		bitmap128.m128i_u32[3]=0;
		bitmap128.m128i_u32[0]=ua.bf[0] ;
		bitmap128.m128i_u32[1]=ua.bf[1] ;
		bitmap128.m128i_u32[2]=ua.bf[2] ;
	}
	inline char * String(char * out){
		BF3 w; // cast BF128 to BF3 
		w.bf[0]=bitmap128.m128i_u32[0];
		w.bf[1]=bitmap128.m128i_u32[1];
		w.bf[2]=bitmap128.m128i_u32[2];
		return w.String(out);
	}
	int String (int * r); // same code as in BF3
	inline int  Count(){return (Count27(bitmap128.m128i_u32[0]) + 
		                        Count27(bitmap128.m128i_u32[1]) +
								Count27(bitmap128.m128i_u32[2])	);	}
	inline int Is0() {return (  !bitmap128.m128i_u32[0]&&
								!bitmap128.m128i_u32[1]&&
								!bitmap128.m128i_u32[2]);}
	inline int IsNot0() {return (bitmap128.m128i_u32[0] ||
								 bitmap128.m128i_u32[1] ||
								 bitmap128.m128i_u32[2]);}
	inline void OrNot(BF128 & o){
		bitmap128.m128i_u32[0]|=(~o.bitmap128.m128i_u32[0]);
		bitmap128.m128i_u32[1]|=(~o.bitmap128.m128i_u32[1]);
		bitmap128.m128i_u32[2]|=(~o.bitmap128.m128i_u32[2]);
	}
	inline void Set(int cell)   {bitmap128.m128i_u32[C_div27[cell]] |= 1<< C_mod27[cell];}
	inline void Clear(int cell) {bitmap128.m128i_u32[C_div27[cell]] &= (~(1<< C_mod27[cell]));}
	inline int NotDisjBF128(BF128 & o){
		return( (bitmap128.m128i_u32[0] & o.bitmap128.m128i_u32[0]) ||
			     (bitmap128.m128i_u32[1] & o.bitmap128.m128i_u32[1]) ||
				 (bitmap128.m128i_u32[2] & o.bitmap128.m128i_u32[2]));
	}
};


inline int BandAndBit_of_Cell(int cell,int &bit){bit=1<< C_mod27[cell];return C_div27[cell];}

#define SHRINKBF128(A) nd=0;for(int i=0;i<no;i++)\
{if(!(vcell & to[i].bitmap128.m128i_u32[A] ))td[nd++]=to[i];}\
return;


inline void ShrinkBF128(BF128 * to,int no, BF128 * td,int & nd,int cell){
	int vcell;
	switch(BandAndBit_of_Cell(cell,vcell)){
	case 0: SHRINKBF128(0)
	case 1: SHRINKBF128(1)
	case 2: SHRINKBF128(2)
	}

}

inline void GetAndT128(BF128 * t,int n,BF128 & and){
	if(n) and=t[0]; else {and.bitmap128.m128i_m128i = _mm_setzero_si128();return;}
	for(int i=1;i<n;i++)  and &= t[i];
} 
inline int IsDisjointT128(BF128 * t,int n,BF128 & v){
	for(int i=0;i<n;i++) if(t[i].isDisjoint(v)) return 1;
	return 0;
}

int IsDisjointT128_2Tables(BF128 * t1,int n1,BF128 * t2,int n2);// if possible first the smallest

//============================
struct PBMI{// 128 bit field with index to a transpose bloc
	bm128 b; //current bit field of still valid UAs or UAH 
	int ii;// index to TRANSPOSE
};


class TRANSPOSE128{// hosting a bloc of 128 BF128 UA (UA high degree) shown as 81x 128 bit fields
public:
	bm128 b[81];
	void Create (BF128 * o, int n);
	void Shrink(TRANSPOSE128 * ot,bm128 * o,int n,bm128 & dest);// not tested not valid
};


class TRANSPOSE32{// hosting a bloc of 32 BF128 UA (UA high degree) shown as 81x 128 bit fields
public:
	int b[81];
	void Create (BF128 * o, int n);
};


struct TUAI;

struct SmallSet   {
   byte size;
   byte data[ 6 ];
};

struct UnavPat   {
   byte digits;             // # of different digits occurring
   SmallSet groups[ 6 ];   // each group consists of those cells containing the same digit
   // we only use groups[ 0 ], ..., groups[ digits - 1 ]
   int GetSize() const      {
      int size = 0;
      for ( int i = 0;  i < digits;  i++ )
         size += groups[ i ].size;
      return size;
   }
   void Print();
 };

struct SPT{
	int ind,lim,ua;
	BF3 bf;
};

struct UA : public BF3{
	int n,cells[12],nstart,ncurrent;
	inline void Initbf(){bf[0]=bf[1]=bf[2]=n=0; }
	inline void operator -=(BF3 & e) {  bf[0] ^=(bf[0] & e.bf[0]);  
	                                   bf[1] ^=(bf[1] &  e.bf[1]);	
									  bf[2] ^= (bf[2] & e.bf[2]);	}
	void Otherbits(){bf[0]^= BIT_SET_27;bf[1]^= BIT_SET_27;bf[2]^= BIT_SET_27;}
	int Compare (UA & x);
	int SupersetOf(UA & x);// assumed *this > x
	void Print(int index=0,int i=0);

};



struct TUA{  // table of unavoidable sets and main operations on it
	char * puz0;
	UA t[1000],wt;
	BF128 t8[1000];
	int nua;
	int diag;
	void PrintAll(){	for(int i=0;i<nua;i++)t[i].Print(1,i);	}
	void PrintAnd(BF3 & and);
	void PrintPerm();
	int AddUA();
	inline void Append(){t[nua++]=wt;}

	void SetNstart();
	
	void SortAll();
	int IsUA_More(BF3 * tx,int nx,BF3 & dead,BF3 & and5);
	void Loadgamex(BF3 & x,int igame=0);
	void Loadgame0(BF3 & x);
	int Go_Perm(BF3 & wbf,BF3 & wbft);
	int SearchMore1();
	int SearchMore2();
	int Search();
	int Search8();
	int Countx(int lim);
	int CountCluesInField(BF3 & mybf,int n0);
	void DumpPath();
	void ListSubsets(BF128 & x,int high=1);
};


struct DYN_BF32{
	struct P32{
		unsigned int v; // 32 bit field
		int ii; // index to TRANSPOSE32 table
	}p[2400];

	int n; // number of valid blocs
	inline void And(DYN_BF32 & o, TRANSPOSE32 * t,int cell){
		n=0;
		for(int i=0;i<o.n;i++){
			P32 & wp=p[n];
			wp=o.p[i];
			wp.v &= t[wp.ii].b[cell];
			if(wp.v) n++;
		}
	}
};



struct DYN_BF{
	PBMI p[600];
	int n; // number of valid blocs
	inline void And(DYN_BF & o, TRANSPOSE128 * t,int cell){
		n=0;
		for(int i=0;i<o.n;i++){
			PBMI & wp=p[n];
			wp=o.p[i];
			wp.b &= t[wp.ii].b[cell];
			if(!(wp.b.isZero())) n++;
		}
	}
};



#define TUAISIZE 160


class UA_XY27{

public:

	struct SPOTNIV{
		//=========== first part
		int cell,cell_old,tdead[81]; 
		BF128 vndead,all_previous_cells;
		inline void Init1(SPOTNIV & o){*this=o;cell_old=-1;o.cell_old=cell;}
		inline void Init(SPOTNIV & o){*this=o;cell_old=-1;o.cell_old=cell;
		                 all_previous_cells.Set(o.cell);}
		inline void Do(int x){cell=x; vndead.Clear(x);tdead[x]=1;}
		//========= direct search and internal loop
		int *tgo,ngo,ui;
		int GetNext();
		int Loop11();
		int Loop12();
		int Loop13();
		int Loop14();
		int Loop15();
	}spots[20];


	struct TUAI{// working on an index of the basic TUA
		int iua[TUAISIZE];
		int ncurrent[TUAISIZE],nua,min_current,i_min_current; //next non hit in direct mode
		UA * t; 
		void Init(TUA & e);
		void Shrink(TUAI & e,SPOTNIV & s); // kill assigned
		void ShrinkOld(); // kill assigned
		void ShrinkFast(); // kill assigned
		void SortAll(); // order UAs by size
		inline int   LoadT0(BF128 * td,BF128 * t8,BF3 dead){
		            BF128 vndead; vndead.Load((~dead));
					int n=0; 
					for(int i=0;i<nua;i++){
					int ii=iua[i];
					td[n]=t8[ii];td[n++]&= vndead;
				}
			}
	}tuai[20];

	struct TUI2{// atstart, all UAs not in TUAI, later, not updated, all remaining UAs
		int iua[300],nua;
		void Init(TUA & e);
		void Shrink(TUI2 & e,SPOTNIV & s); // kill assigned
		void Merge(TUAI & e1,TUI2 & e,SPOTNIV & s); // switch from "optimized" tuai to sequential use
	}tui2[12]; // not changed any more during the second phase


	struct OVERL0{
		BF128 t3[128*100],t4[128*200],t5[128*200],t6[128*100];
		int n3,n4,n5,n6,
			blocs3,blocs4,blocs5,blocs6,
			deb3,deb4,deb5,deb6,
			ntr;
		TRANSPOSE32 tr32[2400];
		TRANSPOSE128 tr[600];
		DYN_BF * mydyn;
		DYN_BF32 * myd32;
		inline void Init(){n3=n4=n5=n6=ntr=0;
				blocs3=blocs4=blocs5=blocs6=0;
				deb3=deb4=deb5=deb6=0;}
		void Create32 ();
		void Create ();
		void PCount32(DYN_BF32 & dbf,int option);
		void PCount(DYN_BF & dbf,int option);
		int SkrinkTable(OVERL0 & oo,DYN_BF & dbf,int deb,int n, bm128 * dest);
		void Shrink32(OVERL0 & oo,DYN_BF & dbf);
		void ShrinkNull(OVERL0 & oo,DYN_BF & dbf);
		void PrintCount(int option);
	private:
		void Add(BF128* t, int n, int & nbl);
		void Add32(BF128* t, int n, int & nbl);
	};

	//======================= start of UA_XY27 data
	//______________________________________________________________________________

	int * rows,*cols,backgrid[82];
	char entry[82],grid[82],
		entry0[82]; // entry switched to 0-8 values
	char ws[82];
	int transpose;
	long long cpt[10];
	int opprint_uas,diag;
	char ptest[82];
	TUA tua0,tua6,tua8,  tuax,tua4,tualast;
	UA *tu;
	DYN_BF dyn_bf[20];
//	DYN_BF32 dyn_bf32[20];
//	OVERL0 ovl0,ovl10,ovlx;
	// data for the search
	BF128  vndead; //currently not valid 

	inline void Initcpt(){memset(cpt,0,sizeof cpt);}

	void CheckPattern( UnavPat & up);
	void CollectAllUas(char * puz);// collect all known UAs in tua0
	void CollectMoreGo1(char * puz,int ir,int ic,int transpose=0);
	void CollectMoreGo(char * puz, int ir,int ic,int transpose=0);
	int Filter17(char * puz);
	void Go1_8_Start();
	int Go1_10();
	void GenUAHSmall(SPOTNIV & s,OVERL0 & b);

	void GenUAHniv8();
	void GenUAHniv8old();
	int Go11();
	void Do_6();
	void Do_7();
	void Do_8();
	void Do_10(int cell);
	int Do_11();
	int Do_12();
	int Do_13();
	int Do_14();
	void DiagGen8(BF128 * t1);
	void WWdiag(int option=0);
};